Since the inception of computers, random numbers have played important roles in areas such as Monte Carlo simulations, probabilistic computing methods (simulated annealing, genetic algorithms, neural networks, and the like), computer-based gaming, and very large scale integration (VLSI) chip-testing. The bulk of the investigation into random (more properly, pseudo-random) number generation methods has been centered around arithmetic algorithms. This is because the prevalent computing medium has been the general purpose, arithmetic computer. Digital hardware designers have long relied on feedback shift registers to generate random numbers.
With the advent of VLSI design, built-in self-tests have become advantageous. In this design, the bulk of the chip testing system is incorporated on the chip itself. Linear feedback shift registers were used initially to implement the random number generation portion of the built-in self-test.
In 1986, Wolfram (S. Wolfram, “Random sequence generation by cellular automata,” Advances in Applied Mathematics, vol. 7, pp. 123-169, June 1986) described a random sequence generation by a simple one-dimensional (1-d) cellular automata with a neighborhood size of three. The work focused on the properties of a particular CA-based RNG dubbed “CA30,” so named due to the decimal value of its truth table. Statistical tests indicated that the CA30 was a superior random number generator to the ones based on linear feedback shift registers. Wolfram suggested that efficient hardware implementation of the CA30 should be possible.
Hortensius et al. (P. D. Hortensius, R. D. McLeod, and H. C. Card, “Parallel number generation for VLSI systems using cellular automata,” IEEE Transactions on Computers, vol. 38, no. 10, pp. 1466-1473, October 1989) described the use of CA30 as a random number generator in an Ising computer. They also described using combinations of CAs (CA90 and CA150), which generated even better random numbers than the CA30. They further indicated that time and site spacing may improve statistical quality of random numbers generated by the CA. Time spacing is where the RNG is advanced more than one step between random number samples and site spacing is where not every bit value generated is used.
Cellular automata (CA) may be thought of as a dynamic system discrete in both time and space. CA may be implemented as an array of cells with homogeneous functionality constrained to a regular lattice of some dimension. For example, in one-dimension, the lattice could be a string (open-ended) or a ring (close-ended), or in two-dimensions, the lattice could be a plane (open-ended) or a toroid (close-ended). Open-ended CAs have boundaries that are fixed and close-ended CAs have boundaries that are periodic.
A function of a CA cell may be represented as a truth table. FIG. 1A shows an exemplary truth table for a four-input CA cell. FIG. 1B shows an exemplary implementation of a cell of the CA. As shown, the cell i implicitly includes a one-bit register. In this instance, there are 16 possible conditions to which a cell may respond (the neighborhood size N is 4 corresponding to the number of inputs). The number of unique responses is 22N or 65,536 (see Table 1 below). In other words, there can be 65,536 unique four-input machines for a given interconnection topology.
Referring back to FIG. 1A, a notation is provided to identify the CA implementing the above function. In essence, the output of the truth table is used as the identification in conjunction with the interconnection notation. As shown, the output of the truth table is converted to a number (from binary to base 16 to decimal). The CA represented by the truth table in FIG. 1A is denoted to be CA06990.
As indicated before, a CA may be made of multiple cells, and the inputs of one cell may connected to the output of other cells. There may even be a feedback contact meaning that one of the inputs of the cell is connected the output of the cell itself. Thus, to uniquely identify a CA, the interconnection topology information should also be provided in addition to it's truth table representation. FIG. 1C illustrates an exemplary notation, a relative displacement notation, which indicates the interconnection topology information of cell i, i.e., how far away the connecting cells are relative to a given four-input cell i.
As an example, FIG. 1D illustrates a 64-cell one-dimensional ring automata network with a displacement of {−1, 0, 1, 2} from the perspective of cell 0. In this instance, each cell i is assumed to have the same displacement value, i.e., all cells have identical functions. In a one-dimensional ring CA network, each cell i has two adjacent neighbors, one on either side. Because the CA network is periodic, cell 63 is adjacent to the cell 0, and thus the displacement of i−1 from cell 0 lands on cell 63.
In a one-dimensional CA network, a relative displacement value {-1, 0, 1, 2} indicates that d8 input of cell i is connected to the output of the cell i−1 (one cell to the left), the d4 input is connected to the output of the cell i itself, the d2 input to cell i+1, and the d1 input to cell i+2. More specifically, from the perspective of cell 0, the inputs d8, d4, d2, and d1 are connected to the outputs of cell 63, itself, cell 1, and cell 2, respectively.
Each cell in the CA network has a state that is updated as a function of its neighbor connections at each time step. In other words, the state of a CA at time t depends on the states of the connected neighbors at time t−1. For a binary CA cell with a neighborhood size of N, there are 22N possible functions. Table 1 illustrates the numbers involved. As Table 1 shows, the universe of possible functions increases extremely rapidly as the number of neighbors N grows.
TABLE 1Neighborhood size N# of Possible Functions142163256465,53654,294,967,29661.84 × 101973.4 × 1038
It is theoretically possible to exhaustively search for viable CA-based RNG. However, in reality, the exhaustive search may be conducted for a small neighborhood size due to the tremendous growth of the search space (truth tables). With modern state of the art computing, N=4 may be the practical limit for exhaustive searches.